package com.gofaraway.service.student.左神算法课.v2;

/**
 * 二分查找
 *
 * @author：ChenPeng
 * @date：2025/4/20 17:33
 */
public class Code01_ErFenFind {


    /**
     * 最简单的二分查找
     *
     * @param arr
     * @param num
     * @return
     */
    public boolean find(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int L = 0;
        int R = arr.length - 1;
        while (L <= R) {
            int mid = (R + L) / 2;

            if (arr[mid] == num) {
                return true;

            } else if (arr[mid] < num) {
                L = mid + 1;
            } else {
                R = mid - 1;
            }
        }

        return false;

    }


    /**
     * 在一个有序数组中，找 >= 某个数最左侧的位置
     *
     * @param arr
     * @param num
     * @return
     */
    public int mostLeftNoLessNumIndex(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        //没找到返回 -1
        int ans = -1;
        int L = 0;
        int R = arr.length - 1;

        while (L <= R) {
            int mid = (L + R) / 2;
            if (arr[mid] >= num) {
                R = mid - 1;
                ans = mid;
            } else {
                L = mid + 1;
            }
        }
        return ans;
    }

    /**
     * 在一个有序数组中，找 <= 某个数最右侧的位置
     *
     * @param arr
     * @param num
     * @return
     */
    public static int mostRightNoLessNumIndex(int[] arr, int num) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        //没找到返回 -1
        int ans = -1;
        int L = 0;
        int R = arr.length - 1;
        while (L <= R) {
            int mid = (L +R)/2;
            if (arr[mid] <= num) {
                ans = mid;
                L = mid + 1;
            } else {
                R = mid -1;
            }
        }
        return ans;
    }



}
